Supply Chain Chaos 📉
Ships are arriving in a scrambled order. We need to calculate the 混沌度（チャウス・メトリクス） (number of inversions) to optimize the AI traffic controller.
逆転とは何か？
A pair of indices $(i, j)$ is an inversion if:
- $i < j$（船 $i$ が船 $j$ より先に到着）
- $A[i] > A[j]$（船 $i$ の優先度識別子が船 $j$ より高い）
Analysis 🔍
例：シーケンス[2, 4, 1, 3, 5]
- ❌ (2, 1)：2は1より前に到着しているが、2 > 1
- ❌ (4, 1)：4は1より前に到着しているが、4 > 1
- ❌ (4, 3)：4は3より前に到着しているが、4 > 3
- 合計の混乱度：3つの逆転
課題
A brute force nested loop is $O(N^2)$.
for i in range(n):
for j in range(i+1, n): ...
for j in range(i+1, n): ...
For $N=100,000$, this takes ~10 billion ops. 結果：実行時間制限超過。